package com.uhu.code;

import com.uhu.code.help.ListNode;

import java.util.Stack;

/**
 * 24. 两两交换链表中的节点
 * https://leetcode.cn/problems/swap-nodes-in-pairs/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution24 {
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode first = new ListNode(0);
        first.next = head;
        Stack<ListNode> st = new Stack<>();
        st.add(first);
        while (head != null) {
            if (st.size() == 1) {
                st.add(head);
                head = head.next;
            } else {
                // 临时节点
                ListNode tempNode = head.next;
                // 修改顺序后的最后一个节点
                ListNode lastNode = st.peek();
                lastNode.next = tempNode;
                head.next = lastNode;
                st.pop();
                if(st.size() == 1) {
                    st.pop().next = head;
                    // 记录last节点
                    st.add(lastNode);
                }
                head = tempNode;
            }
        }
        if(st.size() == 2) {
            // 个数为奇数时多出来的一个节点
            ListNode endNode = st.pop();
            // last节点
            ListNode lastNode = st.pop();
            lastNode.next = endNode;
        }
        return first.next;
    }
}
